package 二叉树题目.输出二叉树的右视图;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 根据前序遍历 和 中序遍历 构建二叉树，并且打印出二叉树右视图
 */
public class Solution {
    public static int i = 0;

    public int[] solve(int[] xianxu, int[] zhongxu) {
        // write code here
        // 1.构建出二叉树
        TreeNode root = buildBinaryTree(xianxu, zhongxu, 0, zhongxu.length - 1);
        // 2.将二叉树每一层节点的值，都存入list中
        ArrayList<ArrayList<Integer>> list = levelOrder(root);
        // 3.循环打印每层最后一个节点的值，保存到数组中
        int[] array = new int[list.size()];
        for (int j = 0; j < list.size(); j++) {
            array[j] = list.get(j).get(list.get(j).size() - 1);
        }
        return array;

    }


    public static TreeNode buildBinaryTree(int[] xianxu, int[] zhongxu, int inbegin,
                                           int inend) {
        if (inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(xianxu[i]);
        // 在中序遍历数组中，找到根节点的位置
        int rootIndex = findIndex(zhongxu, inbegin, inend, xianxu[i]);
        i++;
        root.left = buildBinaryTree(xianxu, zhongxu, inbegin, rootIndex - 1);
        root.right = buildBinaryTree(xianxu, zhongxu, rootIndex + 1, inend);
        return root;
    }

    private static int findIndex(int[] zhongxu, int inbegin, int inend,
                                 int target) {
        for (int j = inbegin; j <= inend; j++) {
            if (zhongxu[j] == target) {
                return j;
            }
        }
        return -1;
    }

    private static ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> arrayList = new ArrayList();
        if (root == null) {
            return arrayList;
        }
        if (root.left == null && root.right == null) {
            ArrayList tmpList = new ArrayList<>();
            tmpList.add(root.val);
            arrayList.add(tmpList);
            return arrayList;
        }
        // 建立个队列
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            ArrayList tmpList = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = deque.poll();
                if (cur.left != null) {
                    deque.offer(cur.left);
                }
                if (cur.right != null) {
                    deque.offer(cur.right);
                }
                tmpList.add(cur.val);
            }
            arrayList.add(tmpList);
        }
        return arrayList;

    }
}
